#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <cctype>
#include <fstream>
using namespace std;

#define lowbit(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define PB push_back
#define MP make_pair
#define MAXN 101000


struct Seq{
	char *junc;
	int njunc;
	int v,j;
	vector<int> muts;

	Seq() {
		muts.clear();
	}
};

inline int SharedMuts(Seq& s1, Seq& s2) {
	int cnt=0;
	int i=0,j=0;
	while (i < s1.muts.size() && j < s2.muts.size()) {
		if (s1.muts[i]<s2.muts[j]) i++;
		else if (s1.muts[i]>s2.muts[j]) j++;
		else {cnt++;i++;j++;}
	}
	return cnt;
}

int tmplv[2][1001];
int tmp[1001];


inline int GetLD(Seq& s1, Seq& s2,int ma=10000) {
	if (s1.njunc==s2.njunc){
		int s=0;
		for (int i=0;i<s1.njunc;i++) s+=(s1.junc[i]!=s2.junc[i]);
		return s;
	}
	else {
		int na=s1.njunc, nb=s2.njunc;
		char* sa=s1.junc;
		char* sb=s2.junc;

		int st=0,en=min(nb,ma);
		bool f=false;
		for (int i=0;i<=en;i++) tmplv[0][i]=i;
		int lna=na;
		for (int i=0;i<na;i++){
			lna--;
			int * la=tmplv[i&1];
			int * cur=tmplv[1-(i&1)];
			cur[st]=la[st]+1;
			for (int j=st;j<en;j++)
				cur[j+1]=min(min(cur[j],la[j+1])+1,la[j]+((sa[i]==sb[j])?0:1));
			if (en<nb)
				cur[en+1]=min(cur[en]+1,la[en]+(sa[i]==sb[en]?0:1));
			if (cur[en+1]+abs(lna-(nb-en-1))<=ma) en++;
			for (;st<=en&&cur[st]+abs(na-i-1-(nb-st))>ma;st++);
			if (st>en) return ma+1;
		}
		return tmplv[na&1][nb];
	}
}

inline double GetScore(Seq& s1, Seq& s2,double thres) {

	int lenPenalty = abs(s1.njunc - s2.njunc)<<1;
	int editLength = min(s1.njunc, s2.njunc);
	if (lenPenalty > thres*editLength-0.001) return thres+1;

	double A = -SharedMuts(s1, s2)*0.35;
	A+= (s1.v^s2.v)?((s1.v^s2.v)>127?8:1):0;
	A+= (s1.j^s2.j)?((s1.j^s2.j)>127?8:1):0;

	if ((max(0.001,0.0+lenPenalty/2+A)+lenPenalty)/(double)editLength>thres)
		return thres+1;

	int tLD=(int)(thres*editLength-lenPenalty-A);

	int LD = GetLD(s1, s2,tLD);

	return (max(0.001,0.0+LD + A)+ lenPenalty ) / (double)editLength;
}




int N;

Seq data[MAXN];

const double THRES=.32;
double delta=.3;
double ANCHORTHRES=1;
double THRESNN=1;

bool vi[MAXN];
vector<int> res;
#define MAXSUB 1111
double sim[MAXSUB][MAXSUB];
int simTime[MAXSUB][MAXSUB];
// vector<vector<double> > sim;
int curTime;

pair<double,int> dist_i[MAXN];
pair<double,int> dist_is[MAXN];
int nxt[MAXN];
int st;
int ndist_i,ndist_is;

int uvipre[MAXN],uvinxt[MAXN],uvist;

void initvi(){
	memset(vi,false,sizeof(vi));
	for (int i=0;i<N;i++){
		uvipre[i]=i-1;
		uvinxt[i]=i+1;
	}
	uvinxt[N-1]=-1;
	uvist=0;
}

inline void visit(int i){
	vi[i]=true;
	int p=uvipre[i];
	int n=uvinxt[i];
	if (p==-1) uvist=n;
	else uvinxt[p]=n;
	if (n!=-1) uvipre[n]=p;
}

vector<int> parts[MAXN];
int ids[MAXN];
bool in[MAXN];
int nstack;
int rid[MAXN];
int sz[MAXN];
int anchornxt[MAXN],anchorprev[MAXN],anchorst,anchorpos[MAXN];

vector<int> sons[MAXN];

double GetScore_M(int i,int j,double THRES){
	if (sons[i].size()>sons[j].size()) swap(i,j);
	int i0=sons[i][0];
	int j0=sons[j][0];

	if (sons[j].size()==1) return GetScore(data[i0],data[j0],THRES);

	int p = (data[i0].v^data[j0].v)?((data[i0].v^data[j0].v)>127?8:1):0;
		p+= (data[i0].j^data[j0].j)?((data[i0].j^data[j0].j)>127?8:1):0;
		p+= GetLD(data[i0], data[j0]);

	int lenPenalty = abs(data[i0].njunc - data[j0].njunc)*2;
	int editLength = min(data[i0].njunc, data[j0].njunc);

	double s=0,ts=THRES*sons[i].size()*sons[j].size();
	for (int q=0;q<sons[i].size();q++){
		for (int w=0;w<sons[j].size();w++){
			s+=(max(0.001,0.0 + p - SharedMuts(data[sons[i][q]], data[sons[j][w]])*0.35)+ lenPenalty ) / (double)editLength;
			if (s>ts) return THRES+1;
		}
	}
	return s/sons[i].size()/sons[j].size();
}

inline void clearanchor(int i){
	int pos=anchorpos[i];
	int p=anchorprev[pos];
	int n=anchornxt[pos];
	if (p==-1) anchorst=n;
	else anchornxt[p]=n;
	anchorprev[n]=p;
}

void solvePart(vector<int> &orid){
	int n=orid.size();
	memset(in,false,sizeof(bool)*n);
	for (int i=0;i<n;i++){
		sz[i]=sons[orid[i]].size();
	}

	for (int i=0;i<ndist_i;i++){
		double s=dist_i[i].first;
		int to=dist_i[i].second;
		if (vi[to]) dist_is[ndist_is++]=MP(s,to);
	}
	if (ndist_is!=n) puts("ERROR 1");

	anchorst=0;
	for (int i=0;i<ndist_is;i++){
		anchorprev[i]=i-1;
		anchornxt[i]=i+1;
		anchorpos[dist_is[i].second]=i;
	}
	int cnt=0;
	for (int z=0;z<n;z++) if (!in[z]){
		cnt++;

		int root=z;
		in[root]=true;
		clearanchor(orid[root]);

		parts[0].clear();
		parts[0].PB(root);

		ids[0]=root;

		for (int q=anchorst;q<ndist_is;q=anchornxt[q]){
			int i=dist_is[q].second;

			if (simTime[rid[i]][root]!=curTime){
				sim[rid[i]][root]=sim[root][rid[i]]=GetScore_M(i,orid[root],THRESNN);
				simTime[rid[i]][root]=simTime[root][rid[i]]=curTime;
			}
		}
		nstack=1;


		for (;nstack;){

			int cur=ids[nstack-1];
			int lacur=-2;
			pair<double,int> best=MP(10,-1);
			if (nstack>1) {
				lacur=ids[nstack-2];
				if (simTime[cur][lacur]==curTime)
					best=MP(sim[cur][lacur],lacur);
			}
			for (int i=0;i<n;i++)
				if (!in[i]&&simTime[i][cur]==curTime&&sim[i][cur]<best.first)
					best=MP(sim[i][cur],i);


			if (nstack>1&&best.second==lacur){

				if (best.first>0.32){
					for (int i=0;i<parts[nstack-1].size();i++)
						res[orid[parts[nstack-1][i]]]=orid[cur];
					nstack--;
					continue;
				}
				//merge
				int nsz=sz[cur]+sz[lacur];

				for (int i=0;i<n;i++){
					if (simTime[i][lacur]!=curTime) continue;
					if (simTime[i][cur]!=curTime) {
						simTime[i][lacur]=simTime[lacur][i]=0;
						continue;
					}
					sim[i][lacur]=sim[lacur][i]=
						(sim[i][lacur]*sz[lacur]+sim[i][cur]*sz[cur])/nsz;
					if (sim[i][lacur]>=THRESNN) simTime[i][lacur]=0;
				}

				for (int i=0;i<parts[nstack-1].size();i++)
					parts[nstack-2].PB(parts[nstack-1][i]);

				sz[lacur]=nsz;
				nstack--;

			}
			else {
				if (best.first<0.32){

					//insert
					int bid=best.second;
					in[bid]=true;
					clearanchor(orid[bid]);

					for (int q=anchorst;q<ndist_is;q=anchornxt[q]){
						int i=dist_is[q].second;

						if (simTime[rid[i]][bid]!=curTime)
						{
							sim[rid[i]][bid]=sim[bid][rid[i]]=GetScore_M(i,orid[bid],THRESNN);
							simTime[rid[i]][bid]=simTime[bid][rid[i]]=curTime;
						}
					}

					parts[nstack].clear();
					parts[nstack].PB(bid);

					ids[nstack++]=bid;

				}
				else {
					//pop
					for (int i=0;i<parts[nstack-1].size();i++)
						res[orid[parts[nstack-1][i]]]=orid[cur];
					nstack--;
				}
			}
		}
	}
}


double sroot[MAXN];

vector<int> vbin[129000],jbin[129000];
bool viv[129000],vij[129000];

int fa[MAXN];

vector<int> gencluster(){

	curTime=1;
	memset(viv,false,sizeof(viv));
	memset(vij,false,sizeof(vij));
	memset(fa,-1,sizeof(fa));
	initvi();
	int fcnt=0;

	double curma=0;

	for (int i=0;i<N;i++){
		for (int j=0;j<vbin[data[i].v].size();j++){
			int k=vbin[data[i].v][j];
			if (data[i].j!=data[k].j) continue;
			if (strcmp(data[i].junc,data[k].junc)==0){
				visit(i);
				fa[i]=k;
				sons[k].PB(i);
				break;
			}
		}
		if (vi[i]) continue;
		sons[i].clear();
		sons[i].PB(i);
		vbin[data[i].v].PB(i);
		jbin[data[i].j].PB(i);
	}

	res.clear();
	for (int i=0;i<N;i++){
		res.PB(i);
	}

	int sid=0;
	for (;uvist!=-1;){
		curTime++;
		int i=uvist;
		visit(i);
		rid[i]=0;

		queue<pair<int,int> > Q;
		for (;Q.size();Q.pop());
		vector<int> cur;cur.clear();
		cur.PB(i);
		ndist_i=ndist_is=0;
		dist_is[ndist_is++]=MP(0,i);



		for (int j=uvist;j!=-1;j=uvinxt[j])
			if ((data[i].v^data[j].v)<128||(data[i].j^data[j].j)<128)
			{
				double sj=GetScore(data[i],data[j],ANCHORTHRES);
				if (sj<ANCHORTHRES){
					sroot[j]=sj;
					dist_i[ndist_i++]=MP(sj,j);
				}
			}
		sort(dist_i,dist_i+ndist_i);



		st=-1;
		int curpos=-1;
		for (int q=0;q<ndist_i;q++){
			int j=dist_i[q].second;
			double sj;

			if (dist_i[q].first<THRES+delta&&(sj=GetScore_M(i,j,THRES))<THRES){
				visit(j);
				Q.push(MP(j,1));
				rid[j]=cur.size();
				cur.PB(j);
				sim[0][rid[j]]=sim[rid[j]][0]=sj;
				simTime[0][rid[j]]=simTime[rid[j]][0]=curTime;
			}
			else {
				if (curpos==-1){
					curpos=q;
					st=q;
				}
				else {
					nxt[curpos]=q;
					curpos=q;
				}
			}
		}
		if (curpos!=-1) nxt[curpos]=-1;




		for (;Q.size();Q.pop()){
			// if (rand()%4) continue;
			int id=Q.front().first;
			int d=Q.front().second;
			double tThres=sroot[id]+THRES+delta;
			int cntq=0;
			for (int q=st,p;q!=-1;){
				if (dist_i[q].first>tThres) break;
				int j=dist_i[q].second;
				double sj;
				if (
					(sj=GetScore_M(id,j,THRES))<THRES){
					visit(j);
					Q.push(MP(j,d+1));
					rid[j]=cur.size();
					cur.PB(j);
					sim[rid[id]][rid[j]]=sim[rid[j]][rid[id]]=sj;
					simTime[rid[id]][rid[j]]=simTime[rid[j]][rid[id]]=curTime;
					if (q==st) {
						q=nxt[q];
						st=q;
					}
					else {
						q=nxt[q];
						nxt[p]=q;
					}
				}
				else {
					p=q;
					q=nxt[q];
				}
			}
		}

		if (cur.size()<3){
			for (int z=1;z<cur.size();z++) res[cur[z]]=cur[0];
		}
		else solvePart(cur);
	}

	for (int i=0;i<N;i++) if (fa[i]!=-1) res[i]=res[fa[i]];


	return res;
}
class ABCSpeedup{
public:


	void parse(vector<string> &json);

	vector <string> cluster(vector <string> &antibody){

		parse(antibody);

		vector<string> res=genResult(gencluster());

		return res;
	}

	vector<string> genResult(vector<int> res){
		vector<string> sres;
		sres.clear();
		for (int i=0;i<res.size();i++){
			char q[100];
			sprintf(q,"%d",res[i]+1);
			sres.PB(q);
		}
		return sres;
	}
};

#define MAXV 1000
struct smap{
	int nxt[MAXV][300];
	int cnt;
	smap(){
		memset(nxt[0],-1,sizeof(nxt[0]));
		cnt=0;
	}
	int getid(const char* s){
		for (int cur=0,i=0;;i++){
			if (s[i]=='"') return cur;
			int cid=s[i];
			if (nxt[cur][cid]==-1){
				nxt[cur][cid]=++cnt;
				memset(nxt[cnt],-1,sizeof(nxt[cnt]));
			}
			cur=nxt[cur][cid];
		}
	}
} vgene,vall,jgene,jall;

void ABCSpeedup::parse(vector<string> &json){
	N=0;
	Seq cur=Seq();

	for (int i=0;i<json.size();i++){
		const char *s=json[i].c_str();
		if (json[i].size()<2) continue;
		if (s[2]=='{'){
			cur.v=(vgene.getid(json[i+3].c_str()+15)<<7)+(vall.getid(json[i+2].c_str()+14));
			cur.j=(jgene.getid(json[i+11].c_str()+15)<<7)+(jall.getid(json[i+9].c_str()+14));
			cur.njunc=json[i+13].size()-19;
			cur.junc=new char[cur.njunc+5];

			strcpy(cur.junc,json[i+13].c_str()+16);

			i+=15;
		}
		else if (s[2]=='}'){
			data[N++]=cur;
			cur=Seq();
		}
		else if (json[i].size()>11&&s[11]=='l'){
			cur.muts.PB(atoi(s+18)*10000+json[i+1][18]*100+json[i+1][20]);
			i+=3;
		}
	}
}
